package 简单.数学;

/**
 * 你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。
 * <p>
 * 给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/arranging-coins
 */
public class 排列硬币_441 {

    public static void main(String[] args) {

        System.out.println(arrangeCoins(8));
    }

    /**
     * 二分法+等差数列
     * 等差数列求和公式：
     * S(n)=n*a1+n(n-1)/2*d
     * n+n(n-1)/2=(n^2+n)/2
     * 其中n代表行数，求小于硬币数的最大值
     *
     * @param n
     * @return
     */
    public static int arrangeCoins(int n) {
        int left = 0, right = n;
        int coins = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (((long) mid * mid + mid) / 2 <= n) {
                coins = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return coins;
    }

}
